1529. Починка забора

Вам нужно починить старый забор, состоящий из набора досок, некоторые из которых сломаны. Доски пронумерованы слева направо в порядке возрастания.

Починка всех досок с i-ой по j-ую включительно (где i ≤ j ) стоит . Чтобы уменьшить общую стоимость ремонта, иногда выгодно чинить даже целые доски. Ваша задача – найти минимальную стоимость ремонта всего забора.

Вход. Каждая строка представляет отдельный тест, описывающий состояние забора. Она состоит только из следующих символов:

· “X” – сломанная доска;

· “.”– целая доска;

Длина строки (забора) не превышает 2500 символов.

Выход. Для каждого теста выведите в отдельной строке минимальную стоимость ремонта всего забора с 4 десятичными цифрами.

Пример входа	Пример выхода
X.X...X.X X.X.....X X.............XX.X.......X...X..	3.0000 2.7321 5.0000

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть boards – строка, содержащая информацию о заборе. Заведем массив c длины 2502, в котором c[i] будет хранить минимальную стоимость, за которую можно починить забор от первой позиции до i - ой, причем c[0] положим равным 0. Тогда дешевле всего починить первые i секции (от первой до i - ой) забора следующим образом:

1. Если i - ая секция цела (boards[i] = ‘.’), то достаточно починить только первые i – 1 секций: c[i] = c[i – 1];

2. Если i - ая секция сломана (boards[i] = ‘X’), то чиним забор от первой до j - ой секции (0 £ j < i), потратив c[j] денег, а затем чиним доски от (j + 1) - ой до i - ой секции за денег. При этом среди всех возможных j следует выбрать такое, для которого сумма c[j] + наименьшая. То есть

c[i] =

При j = 0 весь забор от первой до i - ой секции следует починить при помощи одной новой доски, заплатив денег.

Положив c[0] = 0, последовательно вычисляем c[1], c[2] , …, c[n], где n – длина забора. Ответом задачи будет значение c[n].

Реализация алгоритма

Объявим строку boards, в которой будем хранить состояние забора. В ячейках c[i] храним минимальную стоимость, за которую можно починить забор от первой до i – ой позиции. Значение c[0] положим равным 0.

#define MAX 2502

string boards;

double c[MAX];

Читаем состояние забора, обрабатываем тесты последовательно.

while (cin >> boards)

{

Сделаем так, чтобы забор начинался с позиции 1.

boards = " " + boards;

Положим c[0] = 0.

c[0] = 0;

Вычисляем минимальную стоимость починки части забора от 1 до i, результат заносим в c[i].

for (i = 1; i < boards.length(); i++)

{

c[i] = INF;

if (boards[i] == '.')

c[i] = c[i - 1];

else

for (j = 0; j < i; j++)

c[i] = min(c[i], c[j] + sqrt(1.0 * i - j));

}

Выводим ответ.

printf("%.4lf\n", c[boards.length() - 1]);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(con.hasNext())

{

String boards = con.nextLine();

boards = " " + boards;

double c[] = new double[boards.length()];

c[0] = 0;

for (int i = 1; i < boards.length(); i++)

{

c[i] = 2000000000;

if (boards.charAt(i) == '.')

c[i] = c[i - 1];

else

for (int j = 0; j < i; j++)

c[i] = Math.min(c[i], c[j] + Math.sqrt(1.0 * i - j));

}

System.out.println(c[boards.length() - 1]);

}

con.close();

}

}